Hiperoperadores

HIPEROPERADORES

“El número es el exponente de una operación” (Wittgenstein, Tractatus 6.021)

“Todo lo que se puede descubrir mediante una operación debe existir independientemente de esta operación” (Bertrand Russell)

Operaciones de Orden Superior
Definición

Las operaciones de orden superior son operaciones realizadas mediante la aplicación sucesiva o recursiva de un operador diádico (de dos argumentos).

Si tenemos una expresión del tipo x⊥y siendo x e y dos argumentos del operador diádico ⊥, se plantea la necesidad de una notación que simplifique la especificación de expresiones de las formas


x⊥(x⊥(x⊥(…(x⊥x))))  


((((x⊥x)…)⊥x)⊥x)⊥x

es decir, la especificación de expresiones con un único argumento x repetido n veces y con asociatividad a la derecha y a la izquierda, respectivamente. Las apariciones de x deben de ser 3 o más.

En MENTAL se pueden representar de la manera siguiente:

Expresión	Asociatividad	Especificación
`x⊥(x⊥(x⊥…(x⊥x))))`	Derecha	`((x★n)⊢⊥)∼`
`((((x⊥x)…)⊥x)⊥x)⊥x`	Izquierda	`∼(⊥⊣(x★n))`

En la expresión ∼(⊥⊣(x★n)) se puede prescindir de ∼, puesto que la aociatividad por defecto es por la izquierda.

Pero esta notación, pese a simplificar las cosas, no es suficiente. Si ⊥ es, por ejemplo, el operador potencia ^, queremos poder especificar potencias de potencias (potencias de orden 2), potencias de potencias de potencias (potencias de orden 3), etc. En general, potencias de orden n.

En MENTAL vamos a utilizar la notación siguiente para potencias de niveles superiores:

Expresión	Semántica
`x^n`	`xⁿ`
`x(^^)n`	`x^x^x…x^x` (`n` términos `x`)
`x(^^^)n`	`x(^^)x(^^)x…x(^^)x` (`n` términos `x`)
...	...

Esta notación es similar a las utilizadas por otros autores en la llamada “superpotenciación” [ver Adenda].

Por defecto, la asociatividad es a la izquierda, es decir, la evaluación de la expresión se realiza de izquierda a derecha. Si quisiéramos asociatividad a la derecha, habría que indicar el operador ∼ a la derecha de la expresión, por ejemplo, (x(^^^)n)∼.

En general, para cualquier operador ⊥:

x(⊥★m)n = (⊥★(m−1))⊣(x★n)

Y así tenemos la siguiente definición formal (en forma de expresión genérica recursiva) del hiperoperador diádico ⊥:

⟨( x(⊥★m)n = ((⊥★(m−1))⊣(x★n) ← m>:1 →' x⊥n) )⟩

en donde aparecen 4 parámetros, incluyendo el operador diádico (en negrita).

Por defecto, supone asociatividad a la izquierda. Si quisiéramos asociatividad a la derecha, habría que indicar el operador ∼ a la derecha de la expresión. Y la expresión genérica parametrizada sería la siguiente:

⟨( ( x( ⊥★m )n)∼ = ((⊥★(m−1))⊣( x★n ))∼ ← m>1 →' x⊥n) )⟩

Ejemplos con ^ (exponenciación)

Expresión	Semántica
`2^3`	`2³ = 8`
`(2 ^^ 2)`	`2^2 = 4`
`(2 ^^ 3)`	`(2^2) ^2 = 4^2 = 16`
`(2 ^^ 3)∼`	`2^ (2^2) = 2^4 = 16`
`(2 ^^^ 3)`	`((2 ^^ 2) ^^ 2) = ((2^2) ^^ 2) = (4 ^^ 2) = 4^4 = 256`
`(2 ^^^ 3)∼`	`(2 ^^ (2 ^^ 2))∼ = (2 ^^ (2 ^ 2))∼ = (2 ^^ 4)∼ = 2^ (2^ (2^2)) = 2^ (2^4) = 2^16 = 65536`
`3^2`	`3^2 = 9`
`(3 ^^ 2)`	`3^3 = 3^3 = 27`
`(3 ^^ 3)`	`(3^3) ^3 = 27^3 = 19683`
`(3 ^^ 3)∼`	`3^ (3^3) = 3^27 = 7625593484987`
`(3 ^^^ 3)`	`(3 ^^ 3) ^^ 3)) = (19683 ^^ 3) = ((19683 ^ 19683) ^ 19683)`
`(3 ^^^ 3)∼`	`(3 ^^ (3 ^^ 3))∼ = (3 ^^ 19683)∼ = (3^3^3... ^3)∼` (el 3 repetido 19683 veces)

Ejemplos con v (raiz)

Expresión	Semántica
`2^v2`	`√2`
`(2 ^vv 2)`	`2^v2 = √(√2)`
`(2 ^vv 3)`	`(2^v2)^v2`
`(2 ^vv 3)∼`	`2^v(2^v2)`
`(2 ^vv 4)`	`((2^v2)^v2)^v2`
`(2 ^vv 4)∼`	`2^v(2^v(2^v2))`

Ejemplos con ∪ (unión)

Expresión	Semántica
`a∪3`	`a3`
`(a ∪∪ 5)`	`(((a∪a)∪a)∪a)∪a = aaaaa`
`(a ∪∪ 5)∼`	`a∪(a∪(a∪(a∪a))) = aaaaa`
`(2 ∪∪∪ 3)`	`((2 ∪∪ 2) ∪∪ 2) = ((2 ∪ 2) ∪∪ 2) = (22 ∪∪ 2) = (22 ∪ 22) = 2222`
`(2 ∪∪∪ 3)∼`	`(2 ∪∪ (2 ∪∪ 2)) = (2 ∪∪ (2 ∪ 2)) = (2 ∪∪ 22) = 2∪2∪2∪2∪2∪2∪2∪2∪2∪2∪2∪2∪2∪2∪2∪2∪2∪2∪2∪2∪2∪2 = 2222222222222222222222`

Por definición, establecemos las siguientes equivalencias entre operadores aritméticos:

(++ ≡ *) (** ≡ ^)

Es decir, dos apariciones seguidas de un operador equivalen al operador de orden superior. Por lo tanto,


⟨( x(++)n ≡ x*n )⟩


⟨( x(**)n ≡ x^n )⟩


⟨( x( (++)(++) )n ≡ x^n )⟩

Hiperoperadores contrarios

Hiperoperador contrario a la derecha:

⟨( (x (⊥★n)' y) = z) ↔ (z (⊥★n) y) = x) )⟩

Hiperoperador contrario a la izquierda:

⟨( (x '(⊥★n) y) = z) ↔ (y (⊥★n) z) = x) )⟩

Ejemplos:

x(^')y es raíz de x en base y
x('^)y es log_yx (logaritmo de x en base y)
(x (^^)' y) es la hiperraíz de orden 2 de x en base y, es decir, una expresión z tal que z(^^)y = x
(x '(^^) y ) es el hiperlogaritmo de orden 2 de x en base y, es decir, una expresión z tal que y(^^)z = x

En general,

(x (^★n)' y) es la hiperraíz de orden n de x en base y

(x '(^★n) y) es el hiperlogaritmo de orden n de x en base y

Hiperoperaciones infinitas

Son las que se repiten indefinidamente. Se pueden expresar de la forma

(⊥★n)⊣(x★)

Para el caso de potencia y n=1, tenemos hiperpotencias infinitas:

^⊣( x↔ )

((x^x)^x)^...

que supone asociatividad por la izquierda, que es igual que la asociatividad a la derecha.

Adenda
Superpotenciación

La superpotenciación es un término utilizado para expresar potencias numéricas de orden superior. No hay una notación estándar. Las notaciones más utilizadas son las siguientes:

La notación de Knuth

En 1972, Donald Knuth inventó la notación “flecha” (↑) para representar potencias de orden superior:


m↑n = mⁿ


m↑↑n = m↑m↑m↑…↑m    (n términos)


m↑↑↑n = m↑↑m↑↑m↑↑…↑↑m    (n términos)


m↑↑↑↑n = m↑↑↑m↑↑↑m↑↑↑…↑↑↑m    (n términos)

La segunda expresión se denomina de varias formas: torre de potencias, superpotencia, hiperpotencia, superexponenciación y tetración (que hace referencia a la cuarta operación aritmética, tras la suma, multiplicación y exponenciación).

En todos los casos se supone la asociatividad a la derecha, es decir, la evaluación tiene lugar de derecha a izquierda. Por ejemplo,


2↑3 = 2³ = 8


2↑↑3 = 2↑(2↑2) = 2↑4 = 16


2↑↑↑3 = 2↑↑(2↑↑2) = 2↑↑(2↑2) =2↑↑4 = 2↑(2↑(2↑2)) = 2↑(2↑4) = 2↑16 = 65536

La notación de Conway

La notación de Knuth tiene el inconveniente de que exige especificar las flechas de forma repetitiva. Por ello, John Conway introdujo una notación con flechas horizontales de tres argumentos, siendo el último el número de flechas:

m→n→p ≡ m↑…↑n

p

Por ejemplo,

3→4→6 ≡ 3↑↑↑↑↑↑4 (6 flechas) Knuth cambió posteriormente su notación por m↑^pn, que equivalía a la notación de Conway, en donde p (como superíndice) indica el número de flechas: m→n→p ≡ m↑^pn

La notación “hiper”

Esta notación se basa en la generalización de las definiciones recursivas siguientes:


a+b = 1 + (a+(b − 1))


a*b = a + (a*(b − 1))


a^b = a * (a^(b − 1))

Se define:


a⁽¹⁾b = a+b


a⁽²⁾b = a*b = a⁽¹⁾(a⁽²⁾(b−1))


a⁽³⁾b = a^b = a⁽²⁾(a⁽³⁾(b−1))


a⁽⁴⁾b = a⁽³⁾(a⁽⁴⁾(b−1))

a⁽ⁿ⁾b = a⁽ⁿ⁻¹⁾(a⁽ⁿ⁾(b−1))

Esta última definición (recursiva) es la de la función “hiper”, que es triádica (los argumentos son a, n y b).

Por ejemplo, para el caso n=4,

a⁽⁴⁾b = a^a^…^a^a (b términos)

La relación entre las tres notaciones es la siguiente:

a↑ⁿb ≡ a→b→n ≡ a⁽ⁿ⁺²⁾b

Por ejemplo,


a↑²b  ≡  a↑↑b  ≡  a→b→2  ≡  a⁽⁴⁾b



a↑³b    a↑↑↑b  ≡  a→b→3  ≡  a⁽⁵⁾b

Existe una extensión de la notación hiper para el caso de que se desee asociatividad a la izquierda. Se basa en las definiciones recursivas siguientes:


a+b = (a+(b−1))+1


a*b = (a*(b−1))+a


a^b = (a^(b−1))*a

Se define:


a₍₁₎b = a+b


a₍₂₎b = a*b = (a₍₂₎(b−1))₍₁₎a


a₍₃₎b = a^b = (a₍₃₎(b−1))₍₂₎a


a₍₄₎b = (a₍₄₎(b−1))₍₃₎a


a_(n)b = (a_(n)(b−1))_(n−1)a

Por ejemplo, para el caso n=4 y b=5,

a₍₄₎5 = (((a^a)^a)^a)^a (5 términos)

La función de Ackermann

Las notaciones anteriores (Knuth, Conway, hiper) tienen una estrecha relación con la función de Ackermann. Se trata de una función recursiva, definida en 1928 por Wilhelm Ackermann, y que es muy utilizada en en la teoría de la computación. Se define (de forma recursiva) como sigue:


A(0, n) = n + 1   (n ≥ 0)


A(m, 0) = A(m−1, 1)   (m≥1)


A(m, n) = A(m−1, A(m, n−1))   (m, n≥1)

Una definición equivalente, utilizando la notación de Knuth, es:


A(0, n) = n+1


A(1, n) = 2+(n+3) − 3


A(2, n) = 2*(n+3) − 3


A(3, n) = 2↑(n+3) − 3


A(4, n) = 2↑↑(n+3) − 3


A(5, n) = 2↑↑↑(n+3) − 3

Se cumplen las equivalencias siguientes:


A(m, n)  ≡  2↑^(m−2)(n+3) − 3  ≡  2→(n+3)→(m−2) − 3  ≡  2(m)(n+3) − 3

La función de Ackermann crece extremadamente rápido. Por ejemplo:


A(1, 2) = 4


A(2, 2) = 7


A(3, 2) = 29


A(4, 2)

Los valores

n↑ⁿn ≡ n→n→n ≡ n^{(n + 2)}n

se denominan “números de Ackermann”:


1↑1 = 1


2↑↑2 = 2↑2 = 22 = 4


3↑↑3 = 3↑(3↑3) = 3↑27 = 7625597484987

La función de Ackermann se utiliza con frecuencia como benchmark: para evaluar la capacidad de un compilador en la tarea de optimización de la recursión.

Bibliografía

Clenshaw; C.W.; Olver, F.W.J. Beyond floating point. Journal of the ACM 31 (2): 319–328, Apr. 1984.
Conway, J.H. y Guy, R.K. The Book of Numbers. New York: Springer-Verlag, 1996.
Corless, R.M.; Gonnet, G.H.; Hare, D.E.G,; Jeffrey, D.J.; Knuth, D.E. On the Lambert W Function. Advanced Computational Mathematics, vol. 5, pp. 329-359, 1996.
Donner, John; Alfred Tarski, Alfred. An extended arithmetic of ordinal numbers. Fundamenta Mathematicae 65: 95–127, 1969.
Holmes, W.N. Composite Arithmetic: Proposal for a New Standard. Computer 30 (3): 65–73, Mar. 1997.
Knuth, Donald E. Mathematics and Computer Science: Coping with Finiteness. Science 194 (4271): 1235–1242, Dec. 1976.
Littlewood, J.E. Large Numbers. Mathematical Gazette 32 (300): 163–171, Jul. 1948.